/*
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
*/

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> v;
        int i = 0;
        int n = intervals.size();
        while(i < n && newInterval.start > intervals[i].end)
            v.push_back(intervals[i++]);
        while(i < n && newInterval.end >= intervals[i].start) {
            newInterval.end = max(newInterval.end, intervals[i].end); 
            newInterval.start = min(newInterval.start, intervals[i].start); ++i;
        } 
        v.push_back(newInterval); 
        while(i < n)
            v.push_back(intervals[i++]); 
        return v;
    }
};

#if 0
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> result;
        if (!intervals.size()) {result.push_back(newInterval); return result;}
        // find first interval
        int idx = -1, low = 0, high = intervals.size()-1;
        while (low < high) {
            int mid = (low+high)/2;
            int start_m = intervals[mid].start;
            if (start_m < newInterval.start) {
                low=mid+1;
            } else if (start_m > newInterval.start) {
                high=mid-1;
            } else {    // equal
                idx=mid; break;
            }
        }
        if (idx < 0) idx = (low)?(low-1):low; //first interval could start from (low-1)
        // insert non-overlapping intervals
        for (int i=0; i < idx; i++) result.push_back(intervals[i]);
        // merge with first interval and afterwards
        for (; idx<intervals.size() && intervals[idx].start <= newInterval.end; idx++) {
            if (!IsOverlap(intervals[idx], newInterval)) result.push_back(intervals[idx]);
            else mergeInterval(intervals[idx], newInterval);
        }
        result.push_back(newInterval);
        // insert rest of the interval
        for (int i=idx; i<intervals.size();i++) result.push_back(intervals[i]);
        return result;
    }
private:
    void mergeInterval(Interval &i1, Interval &inew) {
        inew.start = (i1.start <= inew.start)?i1.start:inew.start;
        inew.end = (i1.end >= inew.end)?i1.end:inew.end;
    }
    bool IsOverlap(Interval &i1, Interval &i2) {
        return !(i1.start > i2.end || i1.end < i2.start);
    }
};
#endif
